浅析图计算技术及其在金融业的应用

验“金”室

万物互联的大数据时代，人、事、物之间时刻产生着繁杂多样的联系，数据结构呈现关联复杂的新态势。例如，互联网打破了时间、空间的制约，使得人类在任何时间、地点，可以联系到想要联系的对象，拓宽了人的社交领域，同时也导致社交关系更复杂。再譬如，过去资金往来主要是银行账户之间，而移动支付时代人们可以通过微信、支付宝转账，提升了支付的便捷性，也导致了资金关系更为复杂。 

在该背景下，图计算技术应运而生，灵活的数据建模、高效的关联查询效率、深层次的推理能力，使其在金融行业反欺诈、个性化推荐、信贷风控等领域发挥着重要的价值。

一、图计算技术概述

1.图计算定义

图(Graph)是一种重要的数据结构，由节点V（或称为顶点、实体），与边E（即个体之间的联系）构成，一般将图表示成G(V,E)。图数据的典型例子有网页链接关系、社交网络、商品推荐等。比如，对于社交网络来说，把用户看做顶点，用户之间建立的关系看做边；淘宝的交易网络，是由节点（个人、商品）和边（购买、收藏）构成的图。

图计算是以图作为数据模型来表达问题并予以解决的过程。图计算过程中，会用到图算法。图算法提供了最有效的分析图数据的方法，描述了如何处理图以发现一些定性或者定量的结论，比如利用最短路径算法做好友推荐，计算关系紧密程度；网页排名（PageRank）算法可以用于传播影响力分析，找出问题的中心，也可以做搜索引擎的网页排名；社区发现算法可以识别洗钱或虚假交易等。

2.图计算模型介绍

图计算模型即针对图数据和图计算特点设计实现的计算模型，一般应用于图计算系统中。与传统计算模型相比，图计算模型主要解决以下问题：

• 图计算的频繁迭代带来的读写数据等待和通信开销大的问题。

• 图算法对节点和边的邻居信息的计算依赖问题。

• 图数据的复杂结构使得图算法难以实现分布不均匀的分块上并行计算的问题。 

为提高图计算系统分析计算图数据的能力，图计算系统需要针对图数据和图计算的特点，设计并实现支持频繁迭代操作、细粒度并行计算和通信开销小的全新计算模型，即图计算模型。按照计算对象，图数据计算模型可以分为节点中心计算模型、边中心计算模型、路径中心计算模型和子图中心计算模型四类（如图1所示）。

图1 图计算模型分类

其中，节点中心计算模型提出时间最长，且被多个图计算系统引用，因此将其按计算任务调度方法进一步分为同步计算模型、异步计算模型和混合计算模型三类。本文重点介绍以节点为中心的图计算模型，它是图计算领域的主流。

1

以节点为中心的图计算模型

以节点（顶点）为中心的图计算模型(vertex-centric model) 是Google早先引入的Pregel，随后被GraphLab、PowerGraph 等系统广泛采用。它的基本思想可以总结为“从顶点的角度思考(Think like a Vertex)”。在该模型上实现算法主要需完成“描述计算中顶点行为”的用户自定义函数。

举例来讲，PageRank 计算部分的一轮迭代可以实现为图2描述的形式。在这里，计算被抽象成各个顶点上的运算和顶点间的消息通信。计算中的每一轮迭代都会为每个顶点调用一次该VertexCompute 函数。这样一来，为不同顶点函数的调用就可以并行执行，充分利用单机多核、集群多机的特性。

图2 以节点为中心的模型实现

PageRank一轮迭代计算的示例

2

同步/异步的图计算模型

图计算模型根据通信消息的特性、调度方式的不同可以细分为同步计算模型、异步计算模型和混合计算模型。如图3所示，对于同一个图上的完成相同的计算任务，可以有同步和异步两种不同的算法分别完成。

图3 同步图计算与异步图计算对比

同步计算模型为Pregel根据BSP模型(Bulk Synchronous Parallel：整体同步并行计算模型) 的概念提出，类似于BSP 模型，它规定了图计算迭代的一轮中，通信一定是发生在先后两论迭代之间的同步障（barrier）处。通信包含了批量更新的消息发送以及被接收处理，而两个同步障之间只进行本地计算。亦即，本轮迭代处理的接收到的消息来自于上轮迭代，而本轮发出的消息会在下一轮被接收处理。它具有与BSP 类似的好处——模型简单易懂，正确性容易得到保证。

异步模型的算法由Pearce等人提出，后被GraphLab引入到图计算平台领域。异步图计算由于没有同步障的限制，传递的消息到达后可以立即被处理，这样做的好处首先是没有全局同步的开销，以及并行处理时的负载不均衡下的资源利用率问题可以得到缓解（如图4所示）。

图 4同步执行与异步执行

除此之外，异步算法执行的指令数还可能更少，比如可用于连通分量和最短路径的计算中。图5所示的PageRank计算中，异步执行相对于同步执行具有更快的收敛速度。

图5 异步PageRank相比同步PageRank

显示出更快的收敛速度 [GraphLab]

但是异步计算模型的缺点是对算法有一定的限制，适用性有局限——例如稀疏矩阵与向量相乘(Sparse Matrix-Vector Multiplication，SpMV) 要求各顶点数据同步更新，就难以采用异步计算模型。

在实际情况中，选取更为高效的模型去描述同样的任务是改进算法的一个重要手段。例如，对于相同的任务，如采用异步图模型算法代替原有的同步模型算法，便有机会在降低计算量的同时给予系统更大的调度自由度，可减少负载不均衡的问题。

3.图计算技术挑战

（1）数据规模巨大

目前，从社交关系到金融网络，图数据的规模都增长到极为庞大的阶段。以银行业中的数据图为例，账户代表图中的顶点，而交易代表图中的边。截至2019年末，全国共开立银行账户113.52亿户，同比增长12.07%。2019年期间，全国银行共办理非现金支付业务3310.19亿笔，金额3779.49万亿元，同比分别增长50.25%和0.29%。而随着这些年电子商务和电子支付的兴起，更多的金融交易出现在线上。

表1统计并列出了国内数个支付机构2019年的交易笔数，我们可以看到其中阿里系的支付宝超过2000亿笔，日均6.3亿笔；腾讯系的财付通超过5000亿笔，日均15.09亿笔。

表1 65家支付机构2019年交易情况

在提供了更为丰富的数据信息的同时，这些数以百亿顶点、千亿边的大规模的图数据也为存储和分析处理的系统带来了前所未有的挑战。

（2）数据稀疏

图数据的的一个特点是稀疏，亦即：一个顶点通过不定数量的边与其他无明确规律的顶点相连。通常的图的顶点度数分布都符合如图6所示幂律性质，即度数x越大的顶点所占比例p(x) 越小。

图6 图的幂律度分布

这样的特征会直接导致两个结果：稀疏数据的存取访问随机化和非均匀的数据难以平均划分。目前计算机存储器的访问特性是非常适合顺序数据存取的，但是随机化的访问与此相悖，会导致极大的资源开销。而数据难以均匀划分则给并行处理带来困难。

（3）计算复杂

图算法通过迭代计算实现计算的收敛，但是不同的顶点包含不同数量的边，也需要不同的迭代步数达到收敛。因而，不同的顶点在计算中的执行操作是不同的，这样的操作分化使得任务难以均匀划分，也难以通过单指令流多数据流的硬件实现并行加速。除此之外，广泛存在的数据交叉访问也会给算法并行执行下的数据一致性带来挑战。

（4）数据动态

如今的图数据都包含动态的信息，例如金融转账图实时发生变化。而对于动态图进行实时化分析能够带来更多优势，例如实时化监测预防金融欺诈能够极大程度地降低风险。与此同时，动态数据一个处理的难点是需要实时化地处理不断产生的动态信息，而不能类似静态图进行离线化预处理。这也导致图计算引擎在静态图分析难度的基础上，再叠加上处理动态数据的技术挑战。

二、图计算在金融领域的应用

1.反欺诈

随着互联网的发展，金融欺诈呈现出专业化、产业化、隐蔽性等特点，从单个作案发展为团伙作案，交易手段更隐蔽、交易链路更复杂，这给欺诈识别带来了新的挑战。基于图计算的反欺诈风控手段，可将所有线索串联起来，还原事件全貌，从而有效地识别出欺诈案件（比如身份造假、团体欺诈、代办包装等），更好识别用户欺诈。

基于账户行为、客户信息、账户信息、设备信息等构建复杂关系网络，利用个性化PageRank、Louvain等图算法进行关联计算，可找出与黑名单账户具有共同、间接共同身份（姓名、开户行、身份证、登录IP等）的其他黑账户，进而挖掘欺诈团伙。

2.识别企业关系图谱

随着企业集团化、家族化、多元化发展，集团客户多层交叉持股、股权层层嵌套、隐性股东和股权代持的现象频繁发生，单个客户信用风险的爆发可能引起整个关联客群的风险。基于工商注册信息构建包含企业、高管及关联公司的企业关系图谱，利用图计算技术挖掘企业实际控制人、一致行动人、最终受益人、交叉持股等隐藏关联关系，有助于发现企业之间违规利益输送、集团信用风险。

3.企业担保圈风险防范

联保、互保贷款是在2008年国际金融危机后，中小企业普遍融资难的背景下，监管部门推出的一种新模式。但关联互保、过度担保会导致中小企业担保圈风险累积，特别是在经济下行周期，一旦利益链上某一环资金链断裂，风险快速传染，引发多米诺骨牌效应，导致担保圈内企业信用风险集中大量爆发，成为商业银行区域性、系统性风险的高危点。

金融业早已关注由于客户之间的担保关系、贸易关系、资金往来关系等引起的传导风险。但受限于传统关系型数据库的数据存储方式，在分析多层关系，比如担保圈等特殊拓扑结构时，受到了比较大的限制。利用强连通分量图、广度优先遍历算法等图计算技术，可高效、直观识别出客户是否存在联保、互保、循环保等风险。另外，传统的银行信贷业务只从贷款企业自身资质、业绩、财务特征、担保方式等方面对企业信用进行评价，决定是否贷款以及贷款的额度，但在供应链金融或者担保圈的新形态下，环环相扣、彼此依赖，链条中的一家企业出现风险，就有可能导致风险蔓延。基于知识图谱、机器学习等技术建立信贷风险传导模型，有助于及时发现潜在风险，防范信贷交叉违约风险。

三、总结和展望

图计算技术作为一种新型的计算模型，被广泛应用于金融行业的各个领域，为金融行业风险防控、个性化推荐等开启了新的一扇窗。虽然图计算技术仍面临超大点、实时性等挑战，但近几年TigerGraph、腾讯星图、华为GES等大批商业图计算产品的推出，大大提升了大规模图计算效率，图计算技术渐趋成熟。

往期推荐

FCC30+

长按左边二维码

关注我们不迷路